package 剑指II;

import com.alibaba.fastjson.JSON;

import java.util.*;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-25
 **/

public class Jz084含有重复元素集合的全排列 {

    /**
     * 给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。
     * <p>
     * 示例 1：
     * 输入：nums = [1,1,2]
     * 输出：
     * [[1,1,2],
     * [1,2,1],
     * [2,1,1]]
     * 示例 2：
     * 输入：nums = [1,2,3]
     * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
     *  
     * 提示：
     * 1 <= nums.length <= 8
     * -10 <= nums[i] <= 10
     */

    private List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        this.dfs(nums, new ArrayList<>(), new HashSet<>());
        return this.result;
    }

    private void dfs(int[] arr, List<Integer> path, Set<Integer> set) {

        if (path.size() == arr.length) {
            this.result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < arr.length; i++) {

            if (set.contains(i) || (i > 0 && set.contains(i - 1) && arr[i] == arr[i - 1])) {
                continue;
            }

            path.add(arr[i]);
            set.add(i);
            this.dfs(arr, path, set);
            // O(1)
            path.remove(path.size() - 1);
            set.remove(i);

        }

    }

    public static void main(String[] args) {
        Jz084含有重复元素集合的全排列 n = new Jz084含有重复元素集合的全排列();
        int[] arr = {1, 2, 1};
        List<List<Integer>> result = n.permuteUnique(arr);
        System.out.println(JSON.toJSONString(result));
    }

}
